package com.algorithm.linkedListDecomposition;

import com.algorithm.mergeTwolinked.Node;

public class LinkedListDecomposition {


    public static void main(String[] args) {
        int[] arr = {1,4,3,2,5,2};
        Node l1 = create(arr);
        print(decomposition(l1, 3));

    }

    public static void print(Node head) {
        Node p = head;
        while (p != null) {
            System.out.println(p.getData());
            p = p.getNext();
        }
    }

    public static Node create(int[] arr) {
        Node head = new Node(arr[0], null);
        Node p = head;
        for (int i = 1; i < arr.length; i++) {
            Node node = new Node(arr[i], null);
            p.setNext(node);
            p = node;
        }
        return head;
    }
    public static Node decomposition(Node head, int k) {
        Node head1 = new Node();
        Node head2 = new Node();
        Node p1 = head1;
        Node p2 = head2;
        while(head != null){
            if(head.getData() >= k){
                p2.setNext(head);
                p2 = p2.getNext();
            } else {
                p1.setNext(head);
                p1 = p1.getNext();
            }
            head = head.getNext();
        }
        p1.setNext(head2.getNext());
//        一定不要忘记设null，否则链表成环
        p2.setNext(null);
        return head1.getNext();
    }
}
